
#ifndef GALOISFIELD_HH
#define GALOISFIELD_HH

#include <click/config.h>
#include <click/glue.hh>

CLICK_DECLS


typedef unsigned char uchar;

#define GF_LUT

#define GF_MAX 0xFF
//#define GF_2 // for debugging

/**
 * Currently allow only powers up to 8
 */
template<int power>
class GaloisField {
public:
    static const int size = 1 << power;

    GaloisField() {
        _exp    = new uchar [2*size];
        _log    = new uchar [size];

        // hard-coded
        unsigned int poly = 0435;

        // this is just for acyclicity checking
        uchar max = size-1;
        for (int j = 0; j < size; j++) {
            _log[j] = max;
            _exp[j] = 0;
        }
        unsigned int b = 1;
        for (int j = 0; j < size-1; j++) {
            if (_log[b] != max) {
                click_chatter( "Error: j=%d, b=%d, log[b]=%d, exp[j]=%d (0%o)\n",
                               j, b, _log[b], _exp[j], (b << 1) ^ poly);
                exit(1);
            }
            _log[b] = j;
            _exp[j] = b;
            b = b << 1;
            if (b & size)
                b = (b ^ poly) & (size-1);
        }
        // store two copies for exp to avoid modulo
        for (int j = 0; j < size; j++) {
            _exp[j + size-1] = _exp[j];
        }
#ifdef GF_LUT
        _mul = new uchar[size*size];
        _inv = new uchar[size];
        for (int j = 0; j < size; j++) {
            for (int i = 0; i < size; i++) {
                _mul[i + j*size] = _exp[_log[i] + _log[j]];
            }
            _inv[j] = _exp[size-1 - _log[j]];
        }
#endif
    }
    ~GaloisField() {
        delete [] _exp;
        delete [] _log;
#ifdef GF_LUT
        delete [] _mul;
        delete [] _inv;
#endif
    }

    inline uchar log(uchar value) const {
        return _log[value];
    }

    inline uchar exp(uchar value) const {
        return _exp[value];
    }

    inline uchar add(uchar a, uchar b) const {
        return (a ^ b);
    }

    inline uchar sub(uchar a, uchar b) const {
        return (a ^ b);
    }

    inline uchar mul(uchar a, uchar b) const {
        if ((a == 0) || (b == 0))
            return 0;
#ifdef GF_2
        return 1;
#endif

#ifdef GF_LUT
        return _mul[(int)a + (int)b * size];
#else
        return _exp[_log[a] + _log[b]];
#endif
    }

    inline uchar inverse(uchar val) const {
#ifdef GF_2
        return val;
#endif

#ifdef GF_LUT
        return _inv[val];
#else
        return _exp[size-1 - _log[val]];
#endif
    }

protected:
    uchar* _exp;
    uchar* _log;
#ifdef GF_LUT
    uchar* _mul;
    uchar* _inv;
#endif
};


CLICK_ENDDECLS

#endif
